/*
题目: 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
https://leetcode.cn/problems/longest-valid-parentheses/
 */
public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        //栈, 关键思路: 栈中的目标字符串左边还需要有东西
        Stack<Integer> stack = new Stack<> ();
        int result = 0;
        int n = s.length();
        stack.push(-1);

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') { //如果是左括号
                stack.push(i);
                continue ;
            }
            stack.pop(); //如果一直是右括号, 就会一直更新栈顶
            if (stack.isEmpty()) {
                stack.push(i);
            }
            result = Math.max(result, i - stack.peek());
        }

        return result;
    }
}
